# 91. 解码方法
# https://leetcode-cn.com/problems/decode-ways/



class Solution:
    def numDecodings(self, s):
        if s[0] == '0':
            return 0
        res = [0] * (len(s) + 1)
        res[0], res[1] = 1, 1
        i = 1
        while i < len(s):
            n = int(s[i-1] + s[i])
            if s[i] != '0':
                res[i+1] = res[i]
            if n > 9 and n <= 26:
                res[i+1] += res[i-1]
            if res[i+1] == 0:
                return 0
            i += 1
        return res[len(s)]


print(Solution().numDecodings('10'))